#include"Heap.h"




void HPPrint(HP* php)
{
    assert(php);
    int i = 0;
    for(i = 0; i < php->size; i++)
    {
        printf("%d ", php->a[i]);
    }
    printf("\n");
}
void HPSwap(HPDatatype* x, HPDatatype* y)
{
    HPDatatype tmp = *x;
    *x = *y;
    *y = tmp;
}
void AdjustUP(HPDatatype* a, int child)
{
    int parent = (child - 1) / 2;

    while(child > 0)
    {
        if(a[child] < a[parent])
        {
            HPSwap(&a[child], &a[parent]);

            child = parent;
            parent = (child - 1) / 2;
        }
        else{
            break;
        }
    }
}
void AdjustDown(HPDatatype* a, int size, int parent)
{
    int child = parent * 2 + 1;

    while(child < size)
    {
        if(child + 1 < size && a[child + 1] < a[child])
        {
            child = child + 1;
        }

        if(a[child] < a[parent])
        {
            HPSwap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else{
            break;
        }
    }
}
void HPInit(HP* php)
{
    assert(php);

    php->a = NULL;
    php->capacity = php->size = 0;
}
void HPDeatroy(HP* php)
{
    assert(php);
    if(php->a != NULL)
    {
        free(php->a);
        php->a = NULL;
        php->capacity = php->size = 0;
    }
}
void HPPush(HP* php, HPDatatype x)
{
    assert(php);
    
    if(php->size == php->capacity)
    {
        int newcapacity = php->capacity == 0 ? 4 :php->capacity * 2;
        HPDatatype* tmp = (HPDatatype*)realloc(php->a, sizeof(HPDatatype) * newcapacity);
        if(tmp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newcapacity;
    }
    php->a[php->size] = x;
    php->size++;

    AdjustUP(php->a, php->size - 1);
}
void HPPop(HP* php)
{
    assert(php);

    HPSwap(&php->a[0], &php->a[php->size - 1]);

    php->size--;

    AdjustDown(php->a, php->size, 0);
}
HPDatatype HPTop(HP* php)
{
    assert(php);
    assert(php->size > 0);

    return php->a[0];
}
int HPSize(HP* php)
{
    assert(php);

    return php->size;
}
bool HPEmpty(HP* php)
{
    assert(php);

    return php->size == 0;
}

